package com.lsh.linkedList;

import java.util.Stack;

/**
 * @author ：LiuShihao
 * @date ：Created in 2020/7/29 3:58 下午
 * @desc ：实现链表增删改查
 */
public class LinkedListDemo {
    public static void main(String[] args) {
        Hero hero1 = new Hero(1, "宋江", "及时雨");
        Hero hero2 =new Hero(2,"卢俊义","玉麒麟");
        Hero hero3 =new Hero(3,"吴用","智多星");
        Hero hero4 =new Hero(4,"林冲","豹子头");
        LinkedList linkedList = new LinkedList();
//        linkedList.add(hero1);
//        linkedList.add(hero2);
//        linkedList.add(hero3);
//        linkedList.add(hero4);
        linkedList.addPlus(hero4);
        linkedList.addPlus(hero1);
        linkedList.addPlus(hero2);
        linkedList.addPlus(hero3);
        linkedList.addPlus(hero3);
        System.out.println("~~~~~~~修改前~~~~~~~");
        linkedList.show();
        Hero hero5 =new Hero(5,"林冲冲","豹子头头");
        linkedList.update(hero5);
        System.out.println("~~~~~~~修改后~~~~~~~");
        linkedList.show();
        System.out.println("链表的有效节点是："+linkedList.getlenth());
        linkedList.del(2);
        System.out.println("~~~~~删除后~~~~~");
        linkedList.show();
        System.out.println("链表的有效节点是："+linkedList.getlenth());
        System.out.println("查找的英雄是："+linkedList.find(1));
        System.out.println("倒数第几个英雄是："+linkedList.findLastIndex(1));
        System.out.println("~~~~~反转前~~~~~");
        linkedList.show();
        linkedList.reverseLinkedList();
        System.out.println("~~~~~反转后(改变原有链表)~~~~~");
        linkedList.show();
        System.out.println("~~~~~~~使用栈Stack倒序打印链表~~~~~~~~~~");
        linkedList.reversePrint();
        System.out.println("~~~~~~~使用数组倒序打印链表~~~~~~~~~~");
        linkedList.reverseArr();
        System.out.println("~~~~~~~原来的链表~~~~~~~~~~");
        linkedList.show();


    }
}
class LinkedList{
    //初始化一个头节点，不存放具体的数据
    private Hero head = new Hero(0,"","");

    public Hero getHead() {
        return head;
    }

    public void add(Hero hero){
        //不考虑编号顺序时
        //找到当前链表的最后节点，将这个节点的next指向新节点
        //我们需要一个辅助指针
        Hero temp = head;
        //遍历链表，找到最后节点
        while(true){
            if (temp.next == null){
                break;
            }
            //如果没有找到最后节点，就将temp往后移
            temp= temp.next;
        }
        //当退出while循环时，temp就指向了链表的最后一个元素
        //将最后元素的next指向新节点即可
        temp.next= hero;
    }
    /**
     * 按照编号的顺序来添加英雄
     * 定义一个辅助指针和布尔类型的flag（判断要插入的英雄的编号是否已存在）
     * while循环
     *如果 辅助指针的下一个节点为空 停止
     * 如果辅助指针的下一个节点的编号大于要插入的英雄编号，就找到位置，在temp和temp.next的中间插入
     * 如果辅助指针的下一个节点的编号等于要插入的英雄的编号，就将flag修改为true 说明要插入的编号已经存在
     * 如果都不符合，则辅助指针往后移一位。
     *
     * 当while循环退出，说明找到位置就在temp和temp.next之间
     * 判断flag    为true说明编号存在
     * 为false说明可以插入   将temp的下一个节点指向当前要插入的元素，将当前要插入的元素的下一个节点指向temp.next
     * @param hero
     */
    public void addPlus(Hero hero){
        Hero temp = head;
        Boolean flag = false;
        while(true){
            if (temp.next == null){
                break;
            }
            if (temp.next.no>hero.no){
                break;
            }else if (temp.next.no == hero.no){
                flag = true;
                break;
            }
            temp= temp.next;
        }
        if (flag) System.out.println("编号"+hero.no+"已存在");
        else {
            hero.next = temp.next;
            temp.next = hero;
        }

    }
    /**
     * 先判断链表是否为空，如果为空直接返回
     * 然后定义一个辅助节点temp，将头节点的next赋值给temp
     * 判断temp的next是否为空 如果为空
     */
    public void show(){
        //判断链表是否为空
        if (head.next == null ){
            System.out.println("链表为空！");
            return;
        }
        Hero temp = head.next;
        while(true){
            if (temp == null){
                break;
            }
            //输出节点信息
            System.out.println(temp);
            //将加点后移
            temp = temp.next;
        }
    }

    public void update(Hero hero){
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        Hero temp = head.next;
        Boolean flag = false;
        while(true){
            if (temp == null){
                break;//链表已经遍历结束
            }
            if (temp.no == hero.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.nickName = hero.nickName;
            temp.name = hero.name;
        }else{
            System.out.println("链表中不存在此英雄！");
        }
    }

    public void  del(int no){
        Hero temp = head.next;
        Boolean flag = false;
        while(true){
            if (temp == null){
                break;
            }else if (temp.no == no){
              flag = true;
              break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.next = temp.next;
        }else {
            System.out.println("链表中不存在这个英雄");
        }
    }

    /**
     * 查找链表的有效长度
     * @return
     */
    public  int getlenth(){
        Hero head = this.getHead();
        Hero temp = head.next;
        int length = 0;
        if (temp == null ){
            return 0;
        }
        while(temp != null){
            length++;
            temp = temp.next;
        }
        return length;
    }

    public Hero find(int no){
        Hero temp = head.next;
        Boolean flag= false;
        if (temp == null){
            System.out.println("链表为空");
            return null;
        }
        while(true){
            if (temp == null){
                break;//说明遍历结束，没有找到
            }else if (temp.no == no){
                flag= true;
                break;
            }
            temp = temp.next;//后移一位；
        }
        if (flag){
            return temp;
        }else{
            System.out.println("链表中不存在此英雄！");
            return null;
        }

    }

    /**
     * 查找链表中的倒数第K个元素
     * @param lastIndex
     * @return
     */
    public Hero findLastIndex(int lastIndex){
        int size = this.getlenth();
        //先对lastIndex做一个校验
        if (lastIndex<0 || lastIndex >size)  return  null;
        Hero temp = head.next;
        for (int i = 0; i < size-lastIndex; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 将链表元素反转！难！
     */
    public void reverseLinkedList(){
        Hero head = this.head;
        Hero current = head.next;
        Hero next = null;
        Hero reverseHead = new Hero(0,"","");
        if (current == null || current.next == null){
            return ;
        }
        while(current != null){
            next = current.next;//先将当前节点的下一个 存储起来 ，这样链表就不会断掉
            current.next = reverseHead.next;//  将当前节点的下一个节点 断开  ，指向新头节点的下一个节点！
            reverseHead.next = current;//将当前节点赋值给   新头节点的下一个节点
            current = next;//当前节点往后移
        }
        head.next = reverseHead.next;//实现单链表的反转
        return ;
    }
    public void reversePrint(){
        Hero head = this.head;
        Hero current = head.next;
        if (current == null){
            return;
        }
        Stack<Hero> heroes = new Stack<>();
        while(current != null){
            heroes.push(current);
            current= current.next;
        }
        while (heroes.size()>0){
            System.out.println(heroes.pop());
        }
    }

    public  void reverseArr(){
        Hero head = this.head;
        Hero current = head.next;
        if (current == null){
            return;
        }
        Hero[] arr = new Hero[this.getlenth()];
        for (int i = 0; i < arr.length ; i++) {
            if(current != null){
            arr[i] = current;
            current = current.next;
        }
        }
        for (int i = arr.length-1; i >=0 ; i--) {
            System.out.println(arr[i]);
        }
    }

//    public LinkedList merge(Hero head1,Hero head2){
//        LinkedList linkedList = new LinkedList();
//        if (head1.next == null&& head2.next == null )  return null;
//        if (head1.next == null && head2.next != null ) {
//            linkedList.head = head2;
//            return linkedList;
//        }
//        if (head1.next != null && head2.next == null ) {
//            linkedList.head = head1;
//            return linkedList;
//        }
//        Hero temp = linkedList.head.next;
//        Hero current1 = head1.next;
//        Hero current2 = head2.next;
//
//        while (current1.no<current2.no){
//            temp = current1;
//            current1 = current1.next;
//            temp = temp.next;
//
//        }
//
//    }
}
class Hero{
    public  int no;
    public String name ;
    public String nickName;
    public Hero next;

    public Hero(int no ,String name,String nickName){
        this.no = no;
        this.name= name;
        this.nickName= nickName;
    }
    @Override
    public String toString() {
        return "Hero{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                ", next=" + next +
                '}';
    }
}
